/*
 * NetworkMinCost.java
 *
 * Created on 1 de febrero de 2007, 02:30 PM
 */

package networkFlow;

/**
 *
 * @author tavobula
 */
public class NetworkMinCost {
    private Network G; private int s, t;
    private Edge st[];
    
    private int ST(int v){
        return st[v].other(v);
    }
    
    private void augment(int s, int t){
        int d=st[t].capRto(t);
        for(int v=ST(t); v!=s; v=ST(v))
            if(st[v].capRto(v)<d)
                d=st[v].capRto(v);
        st[t].addflowRto(t,d);
        for(int v=ST(t);v!=s;v=ST(v))
            st[v].addflowRto(v,d);
    }
    
    /*Encuentra los ciclos negativos en la red*/
    
    private int negcyc(){
        for(int i=1;i<G.getV();++i){
            int V=G.getV(), N=0, iteration=0, revisedNodes=0;
            boolean cycle=false;
            int c=-1;
            int[] wt=new int[V];
            for(int v=0; v<V; v++){
                wt[v]=V*290;
                st[v]=null;
            }
            intQueue Q = new intQueue(G.getE());
            wt[i]=0;
            Q.put(i);
            Q.put(V);
            iteration=1;
            revisedNodes=i;
            buscar:
                while(!Q.empty()){
                    int v;
                    while((v=Q.get())==V){
                        if(N++>V) break buscar;
                        iteration=iteration+1;
                        if(iteration==V) cycle=true;
                        Q.put(V);
                    }
                    AdjList A=G.getAdjList(v);
                    for(Edge e=A.beg();!A.end();e=A.nxt()){
                        int w=e.other(v);
                        int cap=e.capRto(w);
                        int cost=-e.costRto(v);
                        int P=wt[v]+cost;
                        if(cap>0&P<wt[w]){
                            wt[w]=P;
                            Q.put(w);
                            st[w]=e;
                            if(cycle){ return buscarCiclo(v);}
                            if(w==revisedNodes){ return buscarCiclo(v);}
                        }
                    }
                }
        }
        return -1;
    }
    
    
    public int buscarCiclo(int iNode){
        java.util.Vector vec=new java.util.Vector();
        int cNode=iNode;
        vec.add(new Integer(iNode));
        for(int v=ST(iNode); v!=iNode; v=ST(v)){
            int i=0;
            while(i<vec.size()){
                int vnode=Integer.parseInt(vec.get(i).toString());
                if(vnode==v){
                    return v;
                }
                i=i+1;
            }
            vec.add(new Integer(v));
        }
        return iNode;
    }


/** Creates a new instance of NetworkMinCost */
public NetworkMinCost(Network G, int s, int t) {
    this.G=G;
    this.s=s;
    this.t=t;
    st=new Edge[G.getV()];
    NetworkMaxFlow M = new NetworkMaxFlow(G, s, t);
    /**System.out.println(NetworkUtilities.cost(G));
    for(int i=0; i<G.getV();++i){
        AdjList A = G.getAdjList(i);
        for(Edge ed=A.beg();!A.end(); ed=A.nxt())
            System.out.println(ed.toString());
    }
    System.out.println("--------------------");**/
    for(int x=negcyc(); x!=-1; x=negcyc()) {
        augment(x,x);}
    
}





}
